package 动态规划;

public class 动规01背包问题 {

    public static void main(String[] args) {
        int[] w = {2,3,1,5,3};
        int [] v = {5,4,7,8,2};
        System.out.println(maxVaule(w, v, 10));
    }

    /**求在该容量下，能得到的最大价值
     * @param w 物品的重量
     * @param v 物品的价值
     * @param bag 背包的容量
    */
    public static int maxVaule(int[] w,int [] v,int bag){
        //无效条件和终止条件
        if(w == null || v == null || bag < 0 || w.length != v.length){
            return 0;
        }
        //否则开始在每一物品中从左到右顺序的判断选择与不选择得到的最大价值
        System.out.println(helper(w, v, 0, bag));
        return help(w,v,0,bag);

    }

    /**
     * 对于存在重复解的问题，采用动态规划去重，达到优化的效率
     * @param w
     * @param v
     * @param i
     * @param bag
     * @return
     */
    private static int helper(int[] w, int[] v, int i, int bag) {
        //状态容器的容量，可以知道，i，rest为两个变量，i的范围为 0 ~ w.length,rest的容量，最大为bag，最小没有下限
        //所以初始化容量，对rest小于0做特殊处理
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];

        //根据初始化递归来填写状态表
        for (int index = N - 1; index >= 0 ; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];//没有选择当前的物品
                //企图选择当前物品
                int p2 = 0;
                if (!((rest - w[index]) < 0)){
                    p2 = v[index] + dp[index + 1][rest-w[index]];
                }
                dp[index][rest] = Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }

    /**
     * 通过一个w，v，和顺序的index，我就可以在bag容量的范围内获取到最大价值
     * @param w 物品的重量
     * @param v 物品的价值
     * @param i 当前在那个物品的位置
     * @param rest 剩余背包的容量
     * @return 返回最大的价值
     */
    private static int help(int[] w, int[] v, int i, int rest) {
        //递归终止条件
        if (i == w.length){
            return 0;
        }
        if (rest < 0){//如果剩余容量0，刚好有重量为0的物品，是可以加入，但是容量 < 0 ，就说明无法继续添加，直接返回
            return  -1;
        }

        //双路递归
        //如果我选择了当前的物品
        int p1 = 0;
        if(rest - w[i] >= 0){//只有在当前容量满足的情况下，我才可以选择
            //那么，选择以后的价值为：当前价值 + 剩余的最大价值
            p1 = v[i] + help(w,v,i+1,rest - w[i]);
        }
        //如果不选择当前物品,那么最大价值为：
        int p2 = help(w,v,i+1,rest);

        //最终返回p1,p2的最大值
        return Math.max(p1,p2);
    }

    //根据递归来该动规
}
